from typing import List


class Solution:
    def maximumNumber(self, num: str, change: List[int]) -> str:
        size = len(num)

        # 寻找开始位置
        start = -1
        for i, ch in enumerate(num):
            v1 = int(ch)
            if change[v1] > v1:
                start = i
                break

        # 寻找结束位置
        end = size
        for i in range(start + 1, size):
            v2 = int(num[i])
            if change[v2] < v2:
                end = i
                break

        # 不需要替换
        if start == -1:
            return num

        ans = []
        for i in range(size):
            if start <= i < end:
                ans.append(str(change[int(num[i])]))
            else:
                ans.append(num[i])

        return "".join(ans)


if __name__ == "__main__":
    print(Solution().maximumNumber(num="132", change=[9, 8, 5, 0, 3, 6, 4, 2, 6, 8]))  # "832"
    print(Solution().maximumNumber(num="021", change=[9, 4, 3, 5, 7, 2, 1, 9, 0, 6]))  # "934"
    print(Solution().maximumNumber(num="5", change=[1, 4, 7, 5, 3, 2, 5, 6, 9, 4]))  # "5"
